The present invention relates to processors and computing devices and more particularly to compiler techniques for optimizing multi-way decision statements and belonging to a set conditions.
Many practical applications require processing of very large amounts of information in a short period of time. One of the basic approaches to minimizing the time to perform such computations is to apply some sort of parallelism, so that tasks which are logically independent can be performed in parallel. This can be done, for example, by executing two or more instructions per machine cycle, i.e., by means of instruction-level parallelism. Thus, in a class of computers using superscalar processing, hardware is used to detect independent instructions and execute them in parallel, often using techniques developed in the early supercomputers.
Another approach to exploiting instruction level parallelism is used by the Very Long Instruction Word (VLIW) processor architectures in which the compiler performs most instruction scheduling and parallel dispatching at compile time, reducing the operating burden at run time. By moving the scheduling tasks to the compiler, a VLIW processor avoids both the operating latency problems and the large and complex circuitry associated with on-chip instruction scheduling logic. Both superscalar and VLIW processors take advantage of techniques know as pipelining for instruction scheduling optimization.
As known, each VLIW instruction includes multiple independent operations for execution by the processor in a single cycle. A VLIW compiler processes these instructions according to precise conformance to the structure of the processor, including the number and type of the execution units, as well as execution unit timing and latencies. The compiler groups the operations into a wide instruction for execution in one cycle. At run time, the wide instruction is applied to the various execution units with little decoding. The execution units in a VLIW processor typically include arithmetic units such as floating point arithmetic units. An example of a VLIW processor that includes floating point execution units is described by R. K. Montoye, et al. in xe2x80x9cDesign of the IBM RISC System/6000 floating point execution unitxe2x80x9d, IBM J.Res. Develop., V. 43 No.1, pp. 61-62, January 1990. Additional examples are provided in U.S. Pat. No. 5,418,975 incorporated herein by reference.
Predicated and speculative computations are employed in VLIW processing as known in the art, see e.g., Parallel and Distributed Computing Handbook, Albert Y. Zomaya, Editor, McGraw-Hill 1996, chapter 21, Superscalar and VLIW Processors, pp. 621-647, incorporated herein by reference. The results of speculatively executed instructions may be retired or discarded.
It is also known that profile data that characterizes program behavior can be obtained by performing test runs of the program. Such a technique is employed, for example, for profiled branch prediction.
Redundant speculative calculations may reduce effectiveness of software pipelining. Such calculations may occur during compilation of multi-way branch statements for VLIW pipelining. In general, multi-way branch statements can be expresses in the C language (used throughout this specification) as follows:
if (expression)
statement(s)
else if (expression)
statement(s)
else if (expression)
statement(s)
else
statement(s)
A xe2x80x9cswitchxe2x80x9d statement is a multi-way decision statement that tests whether an expression matches one of a number of constant values. For example, in C, the switch statement is expressed as follows:
switch (expression)
case constxe2x80x941:
statement(s)
case constxe2x80x942:
case constxe2x80x943:
.
.
.
case const_m:
statement(s)
case const_n:
statements(s)
default:
statement(s)
This multi-way branch in the switch statement is a barrier to flow transformations aimed at efficient use of hardware for predicated and speculative calculations. Implementation of the entire switch statement by constructing a set of conditionals, which are subsequently transformed to the predicated form, may lead to redundant speculative calculations.
Accordingly multi-way decisions, such as in the switch statements, require efficient compilation for software pipelining. Thus, it is desirable to improve compilation of multi-way brunch statements, and in particular switch statements, so as to reduce redundant speculative computations.
Computer method of compiling a multi-way decision statement for VLIW processing is described. The method comprises: (a) generating profile data for a multi-way decision statement, such as a switch statement; identifying at least one most probable alternative of the multi-way decision and a set of constants associated with the identified alternative using the profile data; determining a probable subset of the identified constants based on the profile data; constructing a conditional statement for the identified alternative using the probable subset of constants; and moving out the identified at least one alternative from the multi-way decision statement.
The condition for the alternative that has been moved out of the multi-way decision (e.g., case statement) is constructed using the probable subset of constants so as to form the condition such as illustrated below.
int x; const int c1, c2, . . . , cN;
if (x==c1 ¦¦ x==c2 ¦¦ . . . ¦¦ x==cN) (1)
This condition is then transformed as follows:
If (cmaxxe2x88x92cmin) less than wint (wint is width in bits of integers used in this condition; cmin=min(c1, c2, . . . , cN); cmax=max(c1, c2, . . . , cN)), then the conditional statement (1) is equivalent to:
if (x less than wint andand (1 less than  less than (xxe2x88x92cmin) and cmask) !=0), (2)
where cmask=(1 less than  less than (c1xe2x88x92cmin)¦ . . . ¦ 1 less than  less than (cNxe2x88x92cmin)) is a constant bit mask.
If cmax less than wint expression (2) is simplified as follows:
if (x less than wint andand (1 less than  less than x and cmask2) !=0), (3)
where cmask2=(1 less than  less than c1¦ . . . ¦1  less than  less than cN) 
Expression (3) is further simplified as follows if cmax less than wint and x less than wint:
if ((1 less than  less than x and cmask2) !=0)
FIG. 1 illustrates a high level flowchart of compilation of the switch statement.